package varvelworld.algorithm.DuplicationFinding;

import java.util.ArrayList;
import java.util.List;


public class QuickSort implements IDuplicationFinding {

    @Override
    public List<Long> execute(long[] a) {
        List<Long> result = new ArrayList<Long>();
        quickSort(a, 0, a.length - 1);
        int s = 1;
        for(int i = 1; i < a.length; i++){
            if(a[i - 1] == a[i]){
                s++;
            }else{
                s = 1;
            }
            if(s == 2){
                result.add(a[i]);
            }
        }
        return result;
    }
    
    static public void quickSort(long[] a, int left, int right){
        int m = (left + right) / 2;
        long key = a[m];
        int i = left ,j = right;
        while(i < j){
            while(!(i >= m || key < a[i]))
                ++i;
            if (i < m) {
                a[m] = a[i];
                m = i;
            }
            while (!(j <= m || a[j] < key))
                --j;
            if (j > m) {
                a[m] = a[j];
                m = j;
            }
        }
        a[m] = key;
        if (m - left > 1)
            quickSort(a, left, m - 1);
        if (right - m > 1)
            quickSort(a, m + 1, right);
}

}
